/*
 * @lc app=leetcode id=204 lang=cpp
 *
 * [204] Count Primes
 */
class Solution {
public:
    int countPrimes(int n) {

        if (n < 2) {
            return 0;
        }

        vector<bool> memo(n, true);
        memo[0] = false;
        memo[1] = false;

        for (int i=0; i<=sqrt(n); i++) {
            if (memo[i]) {
                for (int j=i*i; j<n; j+=i) {
                    memo[j] = false;
                }
            }
        }

        int cnt = 0;
        for (auto b : memo) {
            if (b)
                cnt++;
        }

        return cnt;
    }
};

